package array.binarysearch;

/**
 * @ClassName SearchRange
 * @Description TODO
 * @Author lenovo
 * @Date 2023-02-09 20:56
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class SearchRange {
    /**
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     * <p>
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     * <p>
     * 进阶：你可以设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题吗？
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [5,6,7,7,8,8,10], target = 8   ----[4,5]
     * 输出：[3,4]
     * 示例 2：
     * <p>
     * left = 0,right = 6,mid = 3 nums[mid] = 7
     * left = 4,right = 6,mid = 5 nums[mid] = 8 res=5
     * left = 4,right = 4,mid = 4 nums[mid] = 8 res=4
     * left = 4,right = 3 return res=4
     * <p>
     * left = 0,right =6,mid=3 nums[mid] = 7
     * left = 4,right =6,mid=5 nums[mid] = 8
     * left = 5,right =6,mid=5,nums[mid] = 8 res = 5
     * left = 6,right =6,mid=6,nums[mid] = 10 res = 5
     * left = 7 ,right = 6,return res=5
     * <p>
     * <p>
     * 输入：nums = [5,6,7,7,8,8,10], target = 6
     * 输出：[-1,-1]
     * 示例 3：
     * <p>
     * 输入：nums = [], target = 0
     * 输出：[-1,-1]
     * #思路
     */

    public int[] searchRange(int[] nums, int target) {

        int[] res = new int[]{-1, -1};

        res[0] = binarySearch(nums, target, true);
        res[1] = binarySearch(nums, target, false);

        return res;
    }

    private int binarySearch(int[] nums, int target, boolean leftOrRight) {
        int res = -1;

        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) right = mid - 1;
            else if (nums[mid] < target) left = mid + 1;
            else {
                //相等不一定就返回了，因为数组中还会存在多个相同的值，还需要向左找到边界，所以还需要right= mid-1再向左边的区域匹配是否还有相同的target
                //同理 left= mid +1，继续向右边查找target值
                res = mid;
                if (leftOrRight) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return res;
    }


    public static void main(String[] args) {
        Integer a;
        int b;
        SearchRange searchRange = new SearchRange();
        for (int i : searchRange.searchRange(new int[]{5, 7, 7, 8, 8, 8, 10}, 8)) {
            System.out.println(i);
        }
    }
}